#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;

 // Definition for a binary tree node.
 struct TreeNode {
      int val;
      TreeNode *left;
      TreeNode *right;
      TreeNode() : val(0), left(nullptr), right(nullptr) {}
      TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
      TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  };

class info{
public:
    info(TreeNode* head,TreeNode* pre){
        this->head = head;
        this->pre = pre;
    }
public:
    TreeNode* head;
    TreeNode* pre;
};
 
class Solution {
public:
    TreeNode* increasingBST(TreeNode* root) {
        info result = func(root);
        return result.head;

    }
    info func(TreeNode* root){
        if(root==nullptr){
            return info(root,root);
        }
        info infoLeft = func(root->left);
        info infoRight = func(root->right);
        TreeNode* head = (infoLeft.head == nullptr)?root:infoLeft.head;
        TreeNode* pre;
        if(infoLeft.pre==nullptr){
            // pre=root;
        }
        else{
            infoLeft.pre->left = nullptr;
            infoLeft.pre->right = root;
        }
        root->left = nullptr;
        root->right = infoRight.head;
        pre = (infoRight.pre==nullptr)?root:infoRight;
        return info(head,pre);
    }
};

int main(){
    Solution S;
    TreeNode* head = new TreeNode(5);
    head->left = new TreeNode(3);
    head->right = new TreeNode(6);
    head->left->left = new TreeNode(2);
    head->left->right = new TreeNode(4);
    head->left->left->left = new TreeNode(1);
    head->right->right = new TreeNode(8);
    head->right->right->right = new TreeNode(9);
    head->right->right->left = new TreeNode(7);
    TreeNode* root = S.increasingBST(head);
    return 0;
}